//给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素。

// 示例:
// 输入:
// [
//  [ 1, 2, 3 ],
//  [ 4, 5, 6 ],
//  [ 7, 8, 9 ]
// ]
// 输出:  [1,2,4,7,5,3,6,8,9]

#include <iostream>
#include <set>
#include <string>
#include <vector>
#include <Windows.h>
using namespace std;

class Solution {
	int m, n;	//m行数，n列数
public:
	vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
		if (matrix.size() == 0) return {};
		m = matrix.size();
		n = matrix[0].size();
		int i = 0, j = 0;
		vector<int> ret;
		while (i + j <= m + n - 2) {
			ret.push_back(matrix[i][j]);
			vector<int> next = nextCoordinate(i, j);
			i = next[0];
			j = next[1];
		}
		return ret;
	}
private:
	vector<int> nextCoordinate(int i, int j) {
		//行号与列号的和为偶数，向右上角遍历
		if ((i + j) % 2 == 0) {
			//尚未达到边界
			if (i != 0 && j != n - 1) {
				return { i - 1,j + 1 };
			}
			//达到边界
			else {
				if (j + 1 > n - 1) {
					return { i + 1,j };
				}
				else {
					return { i,j + 1 };
				}
			}
		}
		//向左下角遍历
		else {
			//尚未达到边界
			if (j != 0 && i != m - 1) {
				return { i + 1,j - 1 };
			}
			//达到边界
			else {
				if (i + 1 > m - 1) {
					return { i,j + 1 };
				}
				else {
					return { i + 1,j };
				}
			}
		}
	}
};

int main() {
	vector < vector<int>> matrix = { {1, 2, 3}, { 4,5,6 }, { 7,8,9 } };
	Solution s;
	vector<int> result = s.findDiagonalOrder(matrix);
	for (int i : result) {
		cout << i << " ";
	}
	cout << endl;
}